//存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u]
// 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有
//以下属性：
// 
// 不存在自环（graph[u] 不包含 u）。 
// 不存在平行边（graph[u] 不包含重复值）。 
// 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图） 
// 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。 
// 
//
// 二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称
//为 二分图 。 
//
// 如果图是二分图，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
//输出：false
//解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。 
//
// 示例 2： 
//
// 
//输入：graph = [[1,3],[0,2],[1,3],[0,2]]
//输出：true
//解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。 
//
// 
//
// 提示： 
//
// 
// graph.length == n 
// 1 <= n <= 100 
// 0 <= graph[u].length < n 
// 0 <= graph[u][i] <= n - 1 
// graph[u] 不会包含 u 
// graph[u] 的所有值 互不相同 
// 如果 graph[u] 包含 v，那么 graph[v] 也会包含 u 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 
// 👍 316 👎 0

package com.cute.leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

public class IsGraphBipartite {
    public static void main(String[] args) {
        Solution solution = new IsGraphBipartite().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 第一次接触图相关的题目
     * 判断二分图，使用染色法
     * 可以使用深度优先遍历或者广度优先遍历整个图进行染色，遍历过程中如果当前节点已经染过色了，
     * 判断将要染的颜色和当前颜色是否一致
     * 颜色不一致就返回false，否则继续，如果可以成功遍历完图中所有节点则返回true
     * 使用isVisited数组进行判断，值为0代表没有访问过，值为1 和 -1 代表两种颜色
     */

    /**
     * 使用深度优先遍历算法实现的
     */
    public boolean isBipartite(int[][] graph) {
        int[] isVisited = new int[graph.length];//创建数组保存节点访问以及染色状态
        for (int i = 0; i < graph.length; i++) {
            //遍历所有的节点，调用dfs进行访问并染色
            if (isVisited[i] == 0 && !dfs(graph, i, 1, isVisited)) return false;
        }
        return true;
    }

    /**
     * 深度优先算法
     */
    public boolean dfs(int[][] graph, int v, int color, int[] isVisited){
        //如果当前节点被访问过了，那么就返回当前节点的颜色与这次要染的颜色是否一致
        if (isVisited[v]!=0) return isVisited[v] == color;
        //将当前节点进行染色
        isVisited[v] = color;
        for (int vertex:graph[v]){//深度遍历所有的联通节点
            if (!dfs(graph, vertex, -color, isVisited)) return false;
        }
        return true;
    }

    /**
     * 广度优先遍历来实现，需要借助一个额外的queue
     */
    public boolean BFSIsBipartite(int[][] graph) {
        //保存访问信息
        int[] isVisited = new int[graph.length];
        //保存当前层的所有起始节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < graph.length; i++) {
            //// 因为图中可能含有多个连通域，所以我们需要判断是否存在顶点未被访问，若存在则从它开始再进行一轮 bfs 染色。
            if (isVisited[i]!=0) continue;
            queue.offer(i);
            isVisited[i] = 1;//先将当前节点染色为1
            while (!queue.isEmpty()){
                //获取queue头部节点
                Integer v = queue.poll();
                for (int vertex:graph[v]){
                    //如果当前节点联通的节点颜色与当前节点相同则直接返回false
                    if (isVisited[vertex] == isVisited[v]) return false;
                    if (isVisited[vertex]==0){
                        //联通节点没有染色则将联通节点染色为当前节点的相反颜色
                        isVisited[vertex] = -isVisited[v];
                        //将联通节点添加到队列中去
                        queue.offer(vertex);
                    }
                }
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}